#pragma once 
#include<iostream>
#include<assert.h>
using namespace std;
namespace hcc
{
    //链表节点
    template<class T>
    struct list_node
    {
        typedef list_node node;
        T val;
        node* next;
        node* prev;
        list_node(const T& x=T())
            :val(x)
            ,next(nullptr)
            ,prev(nullptr)
        {}
    };
    //链表迭代器
    template<class T,class ref,class ptr>
    struct list_iterator 
    {
        typedef list_node<T> node;
        typedef list_iterator<T,ref,ptr> iterator;
        node* _node;
        list_iterator(node* node=nullptr)
            :_node(node)
        {}
        ptr operator*() const 
        {
            return _node->val;
        }
        ref operator->() const
        {
            return &(operator*());
        }
        bool operator!=(const iterator& d) const 
        {
            return _node!=d._node;
        }
        bool operator==(const iterator& d) const 
        {
            return !(this!=d);
        }
        iterator& operator++()
        {
            _node=_node->next;
            return *this;
        }
        iterator operator++(int)
        {
            iterator tem=(*this);
            ++(*this);
            return tem;
        }
    };
    //链表
    template<class T>
    class list 
    {
        public:
            typedef list_iterator<T,T*,T&> iterator;
            typedef list_iterator<T,const T*,const T&> const_iterator;
            list()
            :_head(new node)
            {
                _head->next=_head;
                _head->prev=_head;
            }
            iterator begin()
            {
                return iterator(_head->next);
            }
            iterator end()
            {
                return iterator(_head);
            }
            const_iterator begin() const 
            {
                return const_iterator(_head->next);
            }
            const_iterator end() const
            {
                return const_iterator(_head);
            }
            void push_back(const T& x)
            {
                node* newnode=new node(x);
                node* tail=_head->prev;
                tail->next=newnode;
                newnode->prev=tail;
                newnode->next=_head;
                _head->prev=newnode;
            }
        private:
            typedef list_node<T> node; 
            node* _head;

    };
}
